Outdoors, mobile computing devices such as handheld smartphones, tablets, and laptops enjoy a robust and relatively accurate location service from Global Positioning System (GPS) satellite signals. However, such GPS signals do not reach indoors, so that providing an indoor location service is challenging. Furthermore, the demand for accurate location information is especially acute indoors. For example, while a few meters of accuracy which is typically obtained from GPS outdoors is generally sufficient for street-level navigation, small differences in locations indoors often have greater importance to people and applications—thus a few meters of error in an estimated location can place someone in a different office within a building, or sometimes even within a different building. In addition, location-aware smartphone applications which are currently available or planned for the near future, including augmented reality-based building navigation, social networking, and retail shopping, demand both a high accuracy and a low response time. A solution that offers a centimeter-accurate location service indoors would help to enable these and other exciting applications in mobile and pervasive computing.
Early indoor location service systems that propose dedicated infrastructure to provide a fine-grained indoor location service include Active Badge [33], which equips mobiles with infrared transmitters and buildings with many infrared receivers; active badges emit unique codes, which are then detected by the infrared sensor and associated with location with a six meter range. The Bat System [34] uses a matrix of RF-ultrasound receivers, each hard-coded with location, deployed on the ceiling indoors. Users wear “Bats” that transmit unique identifiers to the receivers over RF while sending simultaneous ultrasonic “chirps”. Cricket [18] equips buildings with combined RF/ultrasound beacons while mobiles carry RF/ultrasound receivers. Both Bat and Cricket measure time differences between the RF and ultrasound arrival, triangulating location by combining multiple measurements to or from different beacons.
The most widely used RF information is received signal strength (RSS), usually measured in units of whole decibels. While readily available from commodity WiFi hardware at this granularity, the resulting RSS measurements are very coarse compared to direct physical-layer samples, and so incur an amount of quantization error, especially when few readings are present. There are two main lines of work using RSS; the first, pioneered by RADAR [2, 3] builds “maps” of signal strength to one or more access points, achieving an accuracy on the order of meters [22, 28]. Later systems such as Horus [41] use probabilistic techniques to improve localization accuracy to an average of 0.6 meters when an average of six access points are within range of every location in the wireless LAN coverage area, but require large amounts of calibration. While some work has attempted to reduce the calibration overhead [12], mapping generally requires significant calibration effort. Other map-based work has proposed using overheard GSM signals from nearby towers [32], or dense deployments of desktop clients [4]. Recently, Zee [20] has proposed using crowd-sourced measurements in order to perform the calibration step, resulting in an end-to-end median localization error of three meters when Zee's crowd-sourced data is fed into Horus.
The second line of work using RSS are techniques based on mathematical models. Some of these proposals use RF propagation models [21] to predict distance away from an access point based on signal strength readings. By triangulating and extrapolating using signal strength models, TIX [11] achieves an accuracy of 5.4 meters indoors. Lim et al. [13] use a singular value decomposition method combined with RF propagation models to create a signal strength map (overlapping with map-based approaches). They achieve a localization error of about three meters indoors. EZ [8] is a system that uses sporadic GPS fixes on mobiles to bootstrap the localization of many clients indoors. EZ solves these constraints using a genetic algorithm, resulting in a median localization error of between 2-7 meters indoors, without the need for calibration. Other model-based proposals augment RF propagation models with Bayesian probabilistic models to capture the relationships between different nodes in the network [15], and to develop conditions for a set of nodes to be localizable [40]. Still other model-based proposals are targeted towards ad hoc mesh networks [6, 19, 23].
Prior work using angle-of-arrival (AoA) information includes A. Wong et al. [35], who investigate the use of AoA and channel impulse response measurements for localization. While they have demonstrated positive results at a very high SNR (60 dB), typical wireless LANs operate at significantly lower SNRs, and it is unclear such ideas would integrate with a functioning wireless LAN. Niculescu et al. [16] simulate AoA-based localization in an ad hoc mesh network. AoA has also been proposed in CDMA mobile cellular systems [38], in particular as a hybrid approach between TDoA and AoA [9, 36], and also in concert with interference cancellation and ToA [31]. Much other work in AoA uses this technology to solve similar but materially different problems. For example, geo-fencing [27] utilizes directional antennas and a frame coding approach to control APs' indoor coverage boundary. Patwari et al. [17] propose a system that uses the channel impulse response and channel estimates of probe tones to detect when a device has moved, but do not address location. Faria and Cheriton [10] and others [5, 14] have proposed using AoA for location-based security and behavioural fingerprinting in wireless networks. Chen et al. [7] investigate post hoc calibration for commercial off-the-shelf antenna arrays to enable AoA determination, but do not investigate localization indoors.
In summary, some existing solutions for providing indoor locations are based on using radio frequency transmissions, but this has many challenges. First, there are often many objects indoors, which may be located near wireless access points (WAPs) or mobile clients, and these can reflect the energy of the wireless signal in a phenomenon called multipath propagation. This forces an unfortunate trade-off for most existing RF location-based systems: either model this hard-to-predict pattern of multipath fading, or leverage expensive hardware that can sample the wireless signal at a very high rate. In practice, most existing RF systems choose the former option, building maps of multipath signal strength [2, 3, 32, 41], or estimating coarse differences using RF propagation models [11, 13]. Such an approach can achieve an average localization accuracy from 60 cm [41] up to a number of meters, which is too coarse for at least some of the envisaged applications. In addition, although systems based on the combination of ultrasound and RF sensors, such as Active Badge [33], Bat [34], and Cricket [18], have achieved accuracy to the level of centimeters for indoor localization, these systems usually require dedicated infrastructure to be installed in every room in a building—an approach that is expensive, time-consuming, and imposes a considerable maintenance effort.